package com.lazycat.leetcode.editor.cn;
//2023-05-24 21:38:36
//给你一个正整数 n ，请你返回 n 的 惩罚数 。 
//
// n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和： 
//
// 
// 1 <= i <= n 
// i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 10
//输出：182
//解释：总共有 3 个整数 i 满足要求：
//- 1 ，因为 1 * 1 = 1
//- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
//- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
//因此，10 的惩罚数为 1 + 81 + 100 = 182
// 
//
// 示例 2： 
//
// 
//输入：n = 37
//输出：1478
//解释：总共有 4 个整数 i 满足要求：
//- 1 ，因为 1 * 1 = 1
//- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
//- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
//- 36 ，因为 36 * 36 = 1296 ，且 1296 可以分割成 1 + 29 + 6 。
//因此，37 的惩罚数为 1 + 81 + 100 + 1296 = 1478
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 1000 
// 
//
// Related Topics 递归 数学 👍 11 👎 0

class FindThePunishmentNumberOfAnInteger {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new FindThePunishmentNumberOfAnInteger().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int punishmentNumber(int n) {
        int ans = 0;
        for(int i = 1;i<=n;i++){
            int val = i*i;
            if(dfs(val+"",0,i)){
                ans += val;
            }
        }
        return ans;
    }
    private boolean dfs(String str,int index,int target){

        if(index == str.length()){
            return target == 0;
        }

        for(int i = index;i<str.length();i++){

            int cur = Integer.parseInt(str.substring(index,i+1));

            if(target - cur < 0){
                break;
            }

            if(dfs(str,i+1,target-cur)){
                return true;
            }

        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}